The present invention relates to techniques for implementing a propositional reasoner on a parallel processor. More specifically, the invention relates to techniques for implementing an assumption-based truth maintenance system using a massively parallel processor.
A number of articles, including de Kleer, J., "An Assumption-based TMS," Artificial Intelligence, Vol. 28, 1986, pp. 127-162; and de Kleer J., "Extending the ATMS," Artificial Intelligence, Vol. 28, 1986, pp. 163-196; "Problem Solving with the ATMS," Artificial Intelligence, Vol. 28, 1986, pp. 197-224; and de Kleer, J., and Reiter, R., "Foundations of Assumption-based Truth Maintenance Systems: Preliminary Report," Proceedings of the National Conference on Artificial Intelligence, Seattle, Wash., July 1987, pp. 183-188, describe an Assumption-based Truth Maintenance System (ATMS), a propositional inference engine designed to simplify the construction of problem solvers that search complex search spaces efficiently. The ATMS represents problem states with assumptions, which correspond to primary binary choices, and nodes, which correspond to propositions whose truth is dependent on the truth of the assumptions. Dependency relationships among assumptions and nodes are determined by a domain-specific problem solver such as a conventional inference engine. The problem solver presents these relationships to the ATMS as justifications. The ATMS determines which combinations of assumptions are consistent and identifies the conclusions to which they lead.
The ATMS is conventionally implemented by extending a conventional inference engine appropriate to the problem being solved. The extension includes a propositional reasoner and an interface that receives calls from the inference engine, passes them to the propositional reasoner, and returns results to the inference engine. The inference engine, the interface, and the propositional reasoner all run on a single serial processor, such as a serial Lisp machine, through conventional programming techniques.
Vilain, M., "Heterogenous Concurrency in a Parallel Truth Maintenance System," Proceedings, 1988 Spring Symposium Series, Stanford University, March 22-24, 1988, pp. 237-242, which may not be prior art in relation to the present invention, describes a Truth Maintenance System (TMS) on a Multiple Instruction-Multiple Data (MIMD) multiprocessor. The parallel TMS supports a model of belief maintenance in which it operates concurrently with other problem-solving and deduction processes. Belief structures are propositions associated with nodes in a graph, the links being disjunctive clauses that constrain the truth of the nodes to which they are indexed, as illustrated in FIG. 1. Deduction is performed by constraint propagation from a node whose value is determined, with each clause of the node being checked to determine whether it constrains the truth of other nodes. The parallel strategy is to check all of a node's constraints simultaneously, as shown in FIG. 3. Because of propagation between nodes, locking or synchronization is required to prevent separate processes from setting the truth of a node simultaneously, as would occur when two clauses being checked in parallel both support the determination of the same node. A solution is shown in Appendix A. Page 241 discusses alternatives for implementing ATMS in parallel. Page 241 also indicates that exploiting the same sources of parallelism on large-scale SIMD machines is somewhat unpromising; effective SIMD truth maintenance systems may require a different set of techniques.
Charniak, E. and McDermott, D., Introduction to Artificial Intelligence, Addison-Wesley, Reading, Mass., 1985, pp. 255-270, describe conventional search techniques. FIG. 5-2 shows a search space that is a set of all schedules for a scheduling problem. Each schedule in the search space corresponds to a set of values for scheduled events. Pages 259-267 describe a search algorithm, and page 266 describes handling a number of states in a search space by putting states onto a square. Page 266 also describes backtracking, in which the searcher abandons a state and returns to an earlier one upon encountering an obstacle.